10405. Teleportation

One of the farming chores Farmer John dislikes the most is hauling around lots of cow manure. In order to streamline this process, he comes up with a brilliant invention: the manure teleporter! Instead of hauling manure between two points in a cart behind his tractor, he can use the manure teleporter to instantly transport manure from one location to another.

Farmer John's farm is built along a single long straight road, so any location on his farm can be described simply using its position along this road (effectively a point on the number line). A teleporter is described by two numbers x and y, where manure brought to location x can be instantly transported to location y, or vice versa.

Farmer John wants to transport manure from location a to location b, and he has built a teleporter that might be helpful during this process (of course, he doesn't need to use the teleporter if it doesn’t help). Please help him determine the minimum amount of total distance he needs to haul the manure using his tractor.

Input. One line contains four integers: a and b describing the start and end locations, followed by x and y describing the teleporter. All positions are integers in the range 0 ... 100, and they are not necessarily distinct from each-other.

Output. Print a single integer giving the minimum distance Farmer John needs to haul manure in his tractor.

Sample input	Sample output
3 10 8 2	3

SOLUTION

mathematics

Algorithm analysis

Farmer John has the following manure movement options:

· Drive directly from a to b, covering the distance |a – b|;

· Drive a tractor from a to x, teleport from x to y, and then drive the tractor again from y to b. The total distance covered by the tractor is |a – x| + |b – y|;

· Drive a tractor from a to y, teleport from y to x, and then drive the tractor again from x to b. The total distance covered by the tractor is |a – y| + |b – x|;

The smallest of these three values will be the answer.

Example

In the given example, the best strategy is to haul the manure from position 3 to position 2, teleport it to position 8, and then haul it to position 10. The total distance covered by the tractor is therefore 1 + 2 = 3.

Algorithm realization

Read the input data.

scanf("%d %d %d %d", &a, &b, &x, &y);

Find the answer – the minimum of the three values.

res = abs(a - b);

res = min(res, abs(a - x) + abs(b - y));

res = min(res, abs(a - y) + abs(b - x));

Print the answer.

printf("%d\n", res);

Python realization

Read the input data.

a, b, x, y = map(int, input().split())

Find the answer – the minimum of the three values.

res = abs(a - b)

res = min(res, abs(a - x) + abs(b - y))

res = min(res, abs(a - y) + abs(b - x))

Print the answer.

print(res)